package dp.leetcode_53;

public class DPSolution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // dp[i] 表示以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];
        /*
            dp[i]由 dp[i - 1] 的情况决定
            如果 dp[i - 1] >= 0，子数组的和是正收益，选择 dp[i] = dp[i - 1] + nums[i]
            如果 dp[i - 1] < 0，负收益，不选择，dp[i] = nums[i]
         */
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] >= 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }
        // 返回 dp 数组中的最大值即为最大和
        int res = dp[0];
        for (int num : dp) {
            res = Math.max(num, res);
        }
        return res;
    }
}
